这道题一看就是一道强连通分量的题,不会的可以参考我的博客。
当我们用缩点之后,记新图点的个数为。我们枚举原图的每一条边,计算新图中的点的出度。对于点,我们把它的出度记为。那么,会有以下几种情况:
1.没有一个为0,说明每一个点至少有一条连向其他边的有向边,那么新图至少有条边,一定会有一个环(因为条边是一棵树,无论如何加边都会构成环),但缩点后不可能有环,矛盾。
2.只有一个为0,那么这个点一定受到所有奶牛的膜拜,(其他奶牛出度不为0,会膜拜其他奶牛,这样膜来膜去一定会汇集到出度为0的奶牛上,不理解的自行脑补一下)
3.有两个及以上的为0,那么每个人至少得不到一群奶牛(已经缩点,可能不止一头)的支持。直接输出0。
综合以上三点,我们就可以写出正解了:
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
const int MAXN = 10000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];
vector< int > lit_Graph[ MAXN + 5 ];
stack< int > s;
int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int belong[ MAXN + 5 ] , num[ MAXN + 5 ] , Out[ MAXN + 5 ];
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
is[ u ] = 1 , s.push( u );
int v;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
v = Graph[ u ][ i ];
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = min( low[ u ] , low[ v ] );
}
else if( is[ v ] )
low[ u ] = min( low[ u ] , dfn[ v ] );
}
if( dfn[ u ] == low[ u ] ) {
cnt ++;
do{
v = s.top( );
is[ v ] = 0 , s.pop( );
belong[ v ] = cnt;
num[ cnt ] ++;
}while( u != v );
}
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&x,&y);
Graph[ x ].push_back( y );
}
for( int i = 1 ; i <= n ; i ++ )
if( !dfn[ i ] ) Tarjan( i );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
int u = belong[ i ] , v = belong[ Graph[ i ][ j ] ];
if( u != v ) {
lit_Graph[ u ].push_back( v );
Out[ u ] += num[ v ];
}
}
int Ans = 0 , tot = 0;
for( int i = 1 ; i <= cnt ; i ++ )
if( Out[ i ] == 0 ) Ans += num[ i ] , tot ++;
printf("%d",tot >= 2 ? 0 : Ans);
return 0;
}